/*
 *  Arithmetic encoder and decoder of the portable JBIG
 *  compression library
 *
 *  Markus Kuhn -- http://www.cl.cam.ac.uk/~mgk25/jbigkit/
 *
 *  This module implements a portable standard C arithmetic encoder
 *  and decoder used by the JBIG lossless bi-level image compression
 *  algorithm as specified in International Standard ISO 11544:1993
 *  and ITU-T Recommendation T.82.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 *  If you want to use this program under different license conditions,
 *  then contact the author for an arrangement.
 *
 *  It is possible that certain products which can be built using this
 *  software module might form inventions protected by patent rights in
 *  some countries (e.g., by patents about arithmetic coding algorithms
 *  owned by IBM and AT&T in the USA). Provision of this software by the
 *  author does NOT include any licences for any patents. In those
 *  countries where a patent licence is required for certain applications
 *  of this software module, you will have to obtain such a licence
 *  yourself.
 */


#include "sdkGlobal.h"


#if 1

/*
 *  Probability estimation tables for the arithmetic encoder/decoder
 *  given by ITU T.82 Table 24.
 */

const short lsztab[113] =
    {
        0x5a1d, 0x2586, 0x1114, 0x080b, 0x03d8, 0x01da, 0x00e5, 0x006f,
        0x0036, 0x001a, 0x000d, 0x0006, 0x0003, 0x0001, 0x5a7f, 0x3f25,
        0x2cf2, 0x207c, 0x17b9, 0x1182, 0x0cef, 0x09a1, 0x072f, 0x055c,
        0x0406, 0x0303, 0x0240, 0x01b1, 0x0144, 0x00f5, 0x00b7, 0x008a,
        0x0068, 0x004e, 0x003b, 0x002c, 0x5ae1, 0x484c, 0x3a0d, 0x2ef1,
        0x261f, 0x1f33, 0x19a8, 0x1518, 0x1177, 0x0e74, 0x0bfb, 0x09f8,
        0x0861, 0x0706, 0x05cd, 0x04de, 0x040f, 0x0363, 0x02d4, 0x025c,
        0x01f8, 0x01a4, 0x0160, 0x0125, 0x00f6, 0x00cb, 0x00ab, 0x008f,
        0x5b12, 0x4d04, 0x412c, 0x37d8, 0x2fe8, 0x293c, 0x2379, 0x1edf,
        0x1aa9, 0x174e, 0x1424, 0x119c, 0x0f6b, 0x0d51, 0x0bb6, 0x0a40,
        0x5832, 0x4d1c, 0x438e, 0x3bdd, 0x34ee, 0x2eae, 0x299a, 0x2516,
        0x5570, 0x4ca9, 0x44d9, 0x3e22, 0x3824, 0x32b4, 0x2e17, 0x56a8,
        0x4f46, 0x47e5, 0x41cf, 0x3c3d, 0x375e, 0x5231, 0x4c0f, 0x4639,
        0x415e, 0x5627, 0x50e7, 0x4b85, 0x5597, 0x504f, 0x5a10, 0x5522,
        0x59eb
    };

const unsigned char nmpstab[113] =
    {
        1, 2, 3, 4, 5, 6, 7, 8,
        9, 10, 11, 12, 13, 13, 15, 16,
        17, 18, 19, 20, 21, 22, 23, 24,
        25, 26, 27, 28, 29, 30, 31, 32,
        33, 34, 35, 9, 37, 38, 39, 40,
        41, 42, 43, 44, 45, 46, 47, 48,
        49, 50, 51, 52, 53, 54, 55, 56,
        57, 58, 59, 60, 61, 62, 63, 32,
        65, 66, 67, 68, 69, 70, 71, 72,
        73, 74, 75, 76, 77, 78, 79, 48,
        81, 82, 83, 84, 85, 86, 87, 71,
        89, 90, 91, 92, 93, 94, 86, 96,
        97, 98, 99, 100, 93, 102, 103, 104,
        99, 106, 107, 103, 109, 107, 111, 109,
        111
    };

/*
 * least significant 7 bits (mask 0x7f) of nlpstab[] contain NLPS value,
 * most significant bit (mask 0x80) contains SWTCH bit
 */
const unsigned char nlpstab[113] =
    {
        129, 14, 16, 18, 20, 23, 25, 28,
        30, 33, 35, 9, 10, 12, 143, 36,
        38, 39, 40, 42, 43, 45, 46, 48,
        49, 51, 52, 54, 56, 57, 59, 60,
        62, 63, 32, 33, 165, 64, 65, 67,
        68, 69, 70, 72, 73, 74, 75, 77,
        78, 79, 48, 50, 50, 51, 52, 53,
        54, 55, 56, 57, 58, 59, 61, 61,
        193, 80, 81, 82, 83, 84, 86, 87,
        87, 72, 72, 74, 74, 75, 77, 77,
        208, 88, 89, 90, 91, 92, 93, 86,
        216, 95, 96, 97, 99, 99, 93, 223,
        101, 102, 103, 104, 99, 105, 106, 107,
        103, 233, 108, 109, 110, 111, 238, 112,
        240
    };

/*
 * The next functions implement the arithmedic encoder and decoder
 * required for JBIG. The same algorithm is also used in the arithmetic
 * variant of JPEG.
 */


void arith_encode_init(struct jbg_arenc_state *s, int reuse_st)
{
    int i;

    if (!reuse_st)
        for (i = 0; i < 4096; s->st[i++] = 0);
    s->c = 0;
    s->a = 0x10000L;
    s->sc = 0;
    s->ct = 11;
    s->buffer = -1;    /* empty */

    return;
}


void arith_encode_flush(struct jbg_arenc_state *s)
{
    unsigned long temp;

    /* find the s->c in the coding interval with the largest
     * number of trailing zero bits */
    if ((temp = (s->a - 1 + s->c) & 0xffff0000L) < s->c)
        s->c = temp + 0x8000;
    else
        s->c = temp;
    /* send remaining bytes to output */
    s->c <<= s->ct;
    if (s->c & 0xf8000000L)
    {
        /* one final overflow has to be handled */
        if (s->buffer >= 0)
        {
            s->byte_out(s->buffer + 1, s->file);
            if (s->buffer + 1 == MARKER_ESC)
                s->byte_out(MARKER_STUFF, s->file);
        }
        /* output 0x00 bytes only when more non-0x00 will follow */
        if (s->c & 0x7fff800L)
            for (; s->sc; --s->sc)
                s->byte_out(0x00, s->file);
    }
    else
    {
        if (s->buffer >= 0)
            s->byte_out(s->buffer, s->file);
        /* T.82 figure 30 says buffer+1 for the above line! Typo? */
        for (; s->sc; --s->sc)
        {
            s->byte_out(0xff, s->file);
            s->byte_out(MARKER_STUFF, s->file);
        }
    }
    /* output final bytes only if they are not 0x00 */
    if (s->c & 0x7fff800L)
    {
        s->byte_out((s->c >> 19) & 0xff, s->file);
        if (((s->c >> 19) & 0xff) == MARKER_ESC)
            s->byte_out(MARKER_STUFF, s->file);
        if (s->c & 0x7f800L)
        {
            s->byte_out((s->c >> 11) & 0xff, s->file);
            if (((s->c >> 11) & 0xff) == MARKER_ESC)
                s->byte_out(MARKER_STUFF, s->file);
        }
    }

    return;
}


void arith_encode(struct jbg_arenc_state *s, int cx, int pix)
{
    register unsigned lsz, ss;
    register unsigned char *st;
    long temp;


    st = s->st + cx;
    ss = *st & 0x7f;
    lsz = lsztab[ss];


    if (((pix << 7) ^ s->st[cx]) & 0x80)
    {
        /* encode the less probable symbol */
        if ((s->a -= lsz) >= lsz)
        {
            /* If the interval size (lsz) for the less probable symbol (LPS)
             * is larger than the interval size for the MPS, then exchange
             * the two symbols for coding efficiency, otherwise code the LPS
             * as usual: */
            s->c += s->a;
            s->a = lsz;
        }
        /* Check whether MPS/LPS exchange is necessary
         * and chose next probability estimator status */
        *st &= 0x80;
        *st ^= nlpstab[ss];
    }
    else
    {
        /* encode the more probable symbol */
        if ((s->a -= lsz) & 0xffff8000L)
            return;   /* A >= 0x8000 -> ready, no renormalization required */
        if (s->a < lsz)
        {
            /* If the interval size (lsz) for the less probable symbol (LPS)
             * is larger than the interval size for the MPS, then exchange
             * the two symbols for coding efficiency: */
            s->c += s->a;
            s->a = lsz;
        }
        /* chose next probability estimator status */
        *st &= 0x80;
        *st |= nmpstab[ss];
    }

    /* renormalization of coding interval */
    do
    {
        s->a <<= 1;
        s->c <<= 1;
        --s->ct;
        if (s->ct == 0)
        {
            /* another byte is ready for output */
            temp = s->c >> 19;
            if (temp & 0xffffff00L)
            {
                /* handle overflow over all buffered 0xff bytes */
                if (s->buffer >= 0)
                {
                    ++s->buffer;
                    s->byte_out(s->buffer, s->file);
                    if (s->buffer == MARKER_ESC)
                        s->byte_out(MARKER_STUFF, s->file);
                }
                for (; s->sc; --s->sc)
                    s->byte_out(0x00, s->file);
                s->buffer = temp & 0xff;  /* new output byte, might overflow later */
                /* can s->buffer really never become 0xff here? */
            }
            else if (temp == 0xff)
            {
                /* buffer 0xff byte (which might overflow later) */
                ++s->sc;
            }
            else
            {
                /* output all buffered 0xff bytes, they will not overflow any more */
                if (s->buffer >= 0)
                    s->byte_out(s->buffer, s->file);
                for (; s->sc; --s->sc)
                {
                    s->byte_out(0xff, s->file);
                    s->byte_out(MARKER_STUFF, s->file);
                }
                s->buffer = temp;   /* buffer new output byte (can still overflow) */
            }
            s->c &= 0x7ffffL;
            s->ct = 8;
        }
    } while (s->a < 0x8000);

    return;
}


void arith_decode_init(struct jbg_ardec_state *s, int reuse_st)
{
    int i;

    if (!reuse_st)
        for (i = 0; i < 4096; s->st[i++] = 0);
    s->c = 0;
    s->a = 1;
    s->ct = 0;
    s->startup = 1;
    s->nopadding = 0;
    return;
}

/*
 * Decode and return one symbol from the provided PSCD byte stream
 * that starts in s->pscd_ptr and ends in the byte before s->pscd_end.
 * The context cx is a 12-bit integer in the range 0..4095. This
 * function will advance s->pscd_ptr each time it has consumed all
 * information from that PSCD byte.
 *
 * If a symbol has been decoded successfully, the return value will be
 * 0 or 1 (depending on the symbol).
 *
 * If the decoder was not able to decode a symbol from the provided
 * PSCD, then the return value will be -1, and two cases can be
 * distinguished:
 *
 * s->pscd_ptr == s->pscd_end:
 *
 *   The decoder has used up all information in the provided PSCD
 *   bytes. Further PSCD bytes have to be provided (via new values of
 *   s->pscd_ptr and/or s->pscd_end) before another symbol can be
 *   decoded.
 *
 * s->pscd_ptr == s->pscd_end - 1:
 *
 *   The decoder has used up all provided PSCD bytes except for the
 *   very last byte, because that has the value 0xff. The decoder can
 *   at this point not yet tell whether this 0xff belongs to a
 *   MARKER_STUFF sequence or marks the end of the PSCD. Further PSCD
 *   bytes have to be provided (via new values of s->pscd_ptr and/or
 *   s->pscd_end), including the not yet processed 0xff byte, before
 *   another symbol can be decoded successfully.
 *
 * If s->nopadding != 0, the decoder will return -2 when it reaches
 * the first two bytes of the marker segment that follows (and
 * terminates) the PSCD, but before decoding the first symbol that
 * depends on a bit in the input data that could have been the result
 * of zero padding, and might, therefore, never have been encoded.
 * This gives the caller the opportunity to lookahead early enough
 * beyond a terminating SDNORM/SDRST for a trailing NEWLEN (as
 * required by T.85) before decoding remaining symbols. Call the
 * decoder again afterwards as often as necessary (leaving s->pscd_ptr
 * pointing to the start of the marker segment) to retrieve any
 * required remaining symbols that might depend on padding.
 *
 * [Note that each PSCD can be decoded into an infinitely long
 * sequence of symbols, because the encoder might have truncated away
 * an arbitrarily long sequence of trailing 0x00 bytes, which the
 * decoder will append automatically as needed when it reaches the end
 * of the PSCD. Therefore, the decoder cannot report any end of the
 * symbol sequence and other means (external to the PSCD and
 * arithmetic decoding process) are needed to determine that.]
 */

int arith_decode(struct jbg_ardec_state *s, int cx)
{
    register unsigned lsz, ss;
    register unsigned char *st;
    int pix;

    /* renormalization */
    while (s->a < 0x8000 || s->startup)
    {
        while (s->ct <= 8 && s->ct >= 0)
        {
            /* first we can move a new byte into s->c */
            if (s->pscd_ptr >= s->pscd_end)
            {
                return -1;  /* more bytes needed */
            }
            if (*s->pscd_ptr == 0xff)
                if (s->pscd_ptr + 1 >= s->pscd_end)
                {
                    return -1; /* final 0xff byte not processed */
                }
                else
                {
                    if (*(s->pscd_ptr + 1) == MARKER_STUFF)
                    {
                        s->c |= 0xffL << (8 - s->ct);
                        s->ct += 8;
                        s->pscd_ptr += 2;
                    }
                    else
                    {
                        s->ct = -1; /* start padding with zero bytes */
                        if (s->nopadding)
                        {
                            s->nopadding = 0;
                            return -2; /* subsequent symbols might depend on zero padding */
                        }
                    }
                }
            else
            {
                s->c |= (long) *(s->pscd_ptr++) << (8 - s->ct);
                s->ct += 8;
            }
        }
        s->c <<= 1;
        s->a <<= 1;
        if (s->ct >= 0) s->ct--;
        if (s->a == 0x10000L)
            s->startup = 0;
    }

    st = s->st + cx;
    ss = *st & 0x7f;
    lsz = lsztab[ss];


    if ((s->c >> 16) < (s->a -= lsz))
        if (s->a & 0xffff8000L)
            return *st >> 7;
        else
        {
            /* MPS_EXCHANGE */
            if (s->a < lsz)
            {
                pix = 1 - (*st >> 7);
                /* Check whether MPS/LPS exchange is necessary
                 * and chose next probability estimator status */
                *st &= 0x80;
                *st ^= nlpstab[ss];
            }
            else
            {
                pix = *st >> 7;
                *st &= 0x80;
                *st |= nmpstab[ss];
            }
        }
    else
    {
        /* LPS_EXCHANGE */
        if (s->a < lsz)
        {
            s->c -= s->a << 16;
            s->a = lsz;
            pix = *st >> 7;
            *st &= 0x80;
            *st |= nmpstab[ss];
        }
        else
        {
            s->c -= s->a << 16;
            s->a = lsz;
            pix = 1 - (*st >> 7);
            /* Check whether MPS/LPS exchange is necessary
             * and chose next probability estimator status */
            *st &= 0x80;
            *st ^= nlpstab[ss];
        }
    }

    return pix;
}

#endif

